Slide 15: Graph Theory Fundamentals

Distinguishing Graph Structures $G = (V, E)$

A graph $G$ is defined by a set of vertices $V$ and a set of edges $E$ . Understanding whether edges impose directionality is foundational for pathfinding algorithms (e.g., BFS, DFS) and modeling dependencies.

Feature	Undirected Graph	Directed Graph (Digraph)
Edge Representation	$\{u, v\}$ (A set, symmetric)	$(u, v)$ (An ordered pair, asymmetric)
Meaning	Simple connectivity	Flow, Dependency, Hierarchy
Traversal	If $u \to v$ exists, $v \to u$ must also exist implicitly.	$u \to v$ does not imply $v \to u$ .

Degree and The Handshaking Lemma

The degree of a vertex $v$ ( $\text{deg}(v)$ ) is the count of edges incident to it. In directed graphs, we track in-degree ( $\text{indeg}(v)$ ) and out-degree ( $\text{outdeg}(v)$ ).

The Handshaking Lemma (Fundamental Theorem)

For any undirected graph $G=(V, E)$ , the sum of the degrees of all vertices is exactly twice the number of edges:

\sum_{v \in V} \text{deg}(v) = 2 \cdot |E|

Justification: Every edge is counted exactly once at each of its two endpoints.

📝 Interactive Quiz

1. A small undirected graph $G$ has 6 vertices. The degrees of 5 vertices are $3, 1, 2, 4, 3$ . What is the degree of the 6th vertex, and how many edges does $G$ have?

A) Degree: 3, Edges: 8
B) Degree: 1, Edges: 7
C) Degree: 2, Edges: 9
D) Degree: 3, Edges: 7

Hint: The total degree sum must be an even number.

2. An edge in a graph is represented as an ordered pair $(u, v)$ . What does this imply?

A) The graph is undirected.
B) The graph is directed, with a path from $u$ to $v$ .
C) The graph must be weighted.
D) The graph is guaranteed to be a tree.

3. In a directed graph with 10 edges, what is the sum of the in-degrees of all its vertices?

A) 20
B) 10
C) 5
D) Cannot be determined from the information given.

4. Which of the following degree sequences is IMPOSSIBLE for a simple undirected graph with 5 vertices?

A) 2, 2, 2, 2, 2
B) 1, 1, 1, 1, 1
C) 4, 4, 3, 3, 2
D) 1, 2, 3, 4, 0

Hint: Consider the number of vertices with odd degrees.

KEY INSIGHTS

💡 Graph Theory Insights

Parity and Odd Degrees

A necessary consequence of the Handshaking Lemma is that every undirected graph must contain an even number of vertices with odd degrees. If you calculate an odd number of odd-degree vertices, your edge count is incorrect.

Directed Degree Sum

In directed graphs, the total flow into the system must equal the total flow out, and both equal the number of edges:

\sum_{v \in V} \text{indeg}(v) = \sum_{v \in V} \text{outdeg}(v) = |E|

Distinguishing Graph Structures G=(V,E)G = (V, E)G=(V,E)

Degree and The Handshaking Lemma

The Handshaking Lemma (Fundamental Theorem)

Distinguishing Graph Structures $G = (V, E)$